import math,operator

#todo:error process

def combination(elems,k):
    n = len(elems)
    stack = [0]*k 
    lev = 0
    chosen = elems[:k]

    while True:
        chosen[lev] = elems[stack[lev]]
        for i in xrange(lev+1,k):
            stack[i] = stack[lev] + 1
            lev += 1
            chosen[lev] = elems[stack[i]]
        
        yield chosen[:]

        while stack[lev]+k-lev == n and lev >= 0:
            lev -= 1
        if lev < 0:
            break
        stack[lev] += 1

def combination_num(n,k):
    return factorial(n)/factorial(k)/factorial(n-k)

def permutation(elems,k):
    n = len(elems)
    used = [0] * n
    idxs = [0] * k
    chosen = [0] *k
    def _permute(n_used):
        for i in range(n):
            if used[i] == 1:
                continue
            idxs[n_used] = i
            if n_used < k-1:
                used[i] = 1
                for p in _permute(n_used+1):
                    yield p
                used[i] = 0
            else:
                for i,idx in enumerate(idxs):
                    chosen[i] = elems[idx]
                yield chosen
    for p in _permute(0):
        yield p

def permutation_num(n,k):
    return factorial(n)/factorial(n-k)

def factorial(n):
    if n==0:
        return 1
    return reduce(operator.mul,xrange(1,n+1))

##def main():
##    count = 0
##    for c in permutation(range(1,5),4):
##        count += 1
##        print c
##    if count != permutation_num(4,4):
##        print count,permutation_num(4,4)
##        print "wrong"
##main()
